package com.fengdi.book.hard;

import java.util.*;

public class SortAndSelect {

    public static class WiggleSort {
        public void wiggleSort(int[] nums) {
            int len = nums.length;

            int[] help = new int[len];
            System.arraycopy(nums, 0, help, 0, len);
            Arrays.sort(help);
            int N = len;
            for(int i = 1; i < len; i = i + 2) {
                nums[i] = help[--N];
            }

            for(int i = 0; i < len; i = i + 2) {
               nums[i] = help[--N];
            }
        }
    }

    public static class KthSmallest {
        public int kthSmallest(int[][] matrix, int k) {
            List<Integer> list = new ArrayList<>();
            for (int[] ints : matrix) {
                for (int j = 0; j < matrix[0].length; j++) {
                    list.add(ints[j]);
                }
            }

            list.sort((o1, o2) -> {
                if (o1 - o2 == 0) return 0;
                return o1 - o2;
            });
            System.out.println(list);
            return list.get(k - 1);
        }
    }

    public static class FindMedianSortedArrays {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int len1 = nums1.length;
            int len2 = nums2.length;
            int sumLen = len1 + len2;
            if (sumLen == 0) return 0;

            // 借助归并排序
            int i = 0;
            int j = 0;
            List<Integer> list = new ArrayList<>();
            while (i < len1 && j < len2) {
                if(nums1[i] <= nums2[j]) {
                    list.add(nums1[i]);
                    i++;
                }else {
                    list.add(nums2[j]);
                    j++;
                }
            }

            while (i < len1) {
                list.add(nums1[i]);
                i++;
            }

            while (j < len2) {
                list.add(nums2[j]);
                j++;
            }

            if (sumLen % 2 != 0) {
                return list.get(sumLen / 2);
            }else {
                int mid = sumLen / 2;
                return ((double)list.get(mid - 1) + (double)list.get(mid)) / 2;
            }
        }
    }
}
